package Tree;

import javax.xml.soap.Node;
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val=val;
    }
}
public class BinaryTree {
    public TreeNode root=null;
    /*先序遍历的递归和非递归打印*/
    public void preOrder (TreeNode root) {
        if (root == null)return;
        System.out.println(root);
        inOrder(root.left);
        inOrder(root.right);
    }
    public void preOrderStack (TreeNode root) {
        if (root == null)return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty() ){
            root=stack.pop();
            System.out.println(root.val);
           if (root.right != null)stack.push(root.right);
           if (root.left != null) stack.push(root.left);
        }
    }
    /*中序遍历的递归和非递归打印*/
    public void inOrder(TreeNode root) {
        if (root == null)return;
        inOrder(root.left);
        System.out.println(root);
        inOrder(root.right);
    }
    public void inOrderStack(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    root = stack.pop();
                    System.out.println(root.val);
                    root = root.right;
                }
            }
        }
    }
    /*后序遍历的递归和非递归打印*/
    public void postOrder (TreeNode root) {
        if (root == null)return;
        inOrder(root.left);
        inOrder(root.right);
        System.out.println(root);
    }
    public void postOrderStack (TreeNode root) {
        if (root == null)return;
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> cur = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty() ){
            root=stack.pop();
            cur.push(root);
            if (root.left != null) stack.push(root.left);
            if (root.right != null)stack.push(root.right);
        }
        while (!cur.isEmpty()){
            root=cur.pop();
            System.out.println(root.val);
        }
    }
    //层序遍历
    public void levelOrder(TreeNode root){
        if (root == null )return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val);
            if (cur.left != null)queue.add(cur.left);
            if (cur.right != null)queue.add(cur.right);
        }
    }
    //求一颗树的最大深度-递归的方式
    public int maxDepth (TreeNode root) {
        if (root==null)return 0;
        int leftDepth=0;
        int rightDepth=0;
        leftDepth=maxDepth(root.left);
        rightDepth=maxDepth(root.right);
        return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
    }
    //求一棵树的最大宽度-
    public int maxWidth (TreeNode root) {
        if (root == null )return -1;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        HashMap<TreeNode,Integer> levelMap= new HashMap<>();
        levelMap.put(root,1);
        int curLevel=1;//层数
        int curLevelNode =0;//当前层的节点数
        int max= Integer.MIN_VALUE;
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            int curNodeLevel=levelMap.get(cur);
            //获取当前节点的层,是否还在这一层
            if (curNodeLevel == curLevel){
                curLevelNode++;
            }else {
                max = Math.max(max,curLevelNode);
                curLevel++;
                curLevelNode=1;
            }
            if (cur.left != null){
                levelMap.put(cur.left,curNodeLevel+1);
                queue.add(cur.left);
            }
            if (cur.right != null){
                levelMap.put(cur.right,curNodeLevel+1);
                queue.add(cur.right);
            }
        }
        return max;
    }
    /*判断一棵树是否为搜索二叉树的递归与非递归实现*/
    //思路1
    private int preValue=Integer.MIN_VALUE;
    public boolean isBST(TreeNode root){
        if (root == null)return true;
        boolean isLeftBst=isBST(root.left);
        if (!isLeftBst)return false;
        if (root.val <= preValue ){
            return false;
        }else {
            preValue=root.val;
        }
        return isBST(root.right);
    }
    public boolean isBSTStack(TreeNode root){
        if (root == null) {
            return true;
        }else {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    root = stack.pop();
                    if (root.val <= preValue ){
                        return false;
                    }else {
                        preValue=root.val;
                    }
                    root = root.right;
                }
            }
        }
        return true;
    }
    //思路2-构造信息直接判断
    public class ReturnData{
        public boolean isBST;
        public int min;
        public int max;

        public ReturnData(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }
    public boolean isBST3(TreeNode root){
        ReturnData data=processData(root);
        return data.isBST&& data.max < root.val && data.min > root.val;
    }
    public ReturnData processData(TreeNode x){
        if ( x == null)return null;
        ReturnData leftData=processData(x.left);
        ReturnData rightData=processData(x.right);

        int min = x.val;
        int max = x.val;
        if (leftData != null){
               min=Math.min(min,leftData.min);
               max=Math.max(max,leftData.max);
        }
        if (rightData != null){
            min=Math.min(min,rightData.min);
            max=Math.max(max,rightData.max);
        }
        boolean isBST=true;
        /*俩种违规条件-不是平衡二叉树,最大值大于节点值*/
        if (leftData != null && (!leftData.isBST || leftData.max >= x.val)){
            isBST=false;
        }
        if (rightData != null && (!rightData.isBST || rightData.min <= x.val)){
            isBST=false;
        }
        return new ReturnData(true,min,max);
    }



    /*判断是否是完全二叉树*/
    public boolean isCBT(TreeNode root){
        if (root == null)return true;
        Queue<TreeNode> queue=new LinkedList<>();
        boolean leaf=false;//判断是否遇到俩个左右孩子不双全的节点
        TreeNode l =null;
        TreeNode r=null;
        queue.add(root);
        while (!queue.isEmpty()){
            root = queue.poll();
            l=root.left;
            r=root.right;
            //判断失败逻辑的俩种情况
            if ((leaf && (l != null || r != null)) || (l == null && r != null)){
                return false;
            }
            if (l !=null){
                queue.add(l);
            }
            if (r != null){
                queue.add(r);
            }
            if (l == null || r == null){
                leaf = true;
            }
        }
        return true;
    }

    /*判断一颗二叉树是不是平衡二叉树*/
    public class ReturnType{
        public boolean isBlanced;
        public int height;

        public ReturnType(boolean isBlanced, int height) {
            this.isBlanced = isBlanced;
            this.height = height;
        }
    }
    public boolean isBalance(TreeNode root){
        if (root == null)return true;
        ReturnType type=processType(root);
        return type.isBlanced;
    }
    public ReturnType processType(TreeNode x){
        if (x == null)return new ReturnType(true,0);
        ReturnType leftData=processType(x.left);
        ReturnType rightdata=processType(x.right);
        int height=Math.max(leftData.height,rightdata.height)+1;

        boolean isBalanced=(leftData.isBlanced&&rightdata.isBlanced)&&(Math.abs(leftData.height-rightdata.height)<=1);
        return new ReturnType(isBalanced,height);
    }



    /*判断一颗树是不是满二叉树*/
    public boolean isFull(TreeNode root){
        if (root == null) return true;
        Info data=processInfo(root);
       return data.nodes == (1 << data.height -1);
    }
    public class Info{
        public int height;
        public int nodes;
        public Info(int h,int n){
            height=h;
            nodes=n;
        }
    }
    public Info processInfo(TreeNode x){
        if (x == null) return new Info(0,0);
        Info leftData=processInfo(x.left);
        Info rightData=processInfo(x.right);
        int height = Math.max(leftData.height,rightData.height)+1;
        int nodes = leftData.nodes+rightData.nodes;
        return new Info(height,nodes);
    }

    /*最近公共祖先--不抽象*/
    public TreeNode LCA(TreeNode root ,TreeNode n1,TreeNode n2){
        HashMap<TreeNode,TreeNode> fatherMap=new HashMap<>();
        fatherMap.put(root,root);
        processLCA(root,fatherMap);
        HashSet<TreeNode> set=new HashSet<>();
        TreeNode cur=n1;
        while (cur != fatherMap.get(cur)){
            set.add(cur);
            cur=fatherMap.get(cur);
        }
        cur=n2;
        while (cur != fatherMap.get(cur)){
            if (set.contains(cur)){
                return cur;
            }
            cur=fatherMap.get(cur);
        }
        return null;

    }
    private void processLCA(TreeNode root,HashMap<TreeNode,TreeNode> fatherMap){
        if (root == null)return;
        fatherMap.put(root.left,root);
        fatherMap.put(root.right,root);
        processLCA(root.left,fatherMap);
        processLCA(root.right,fatherMap);
    }

    /*最近公共祖先,递归方式-抽象
    * 要分类:n1 是 n2 的最近公共祖先或 n2 是 n1 的最近公共祖先
    * n1 与n2 不为公共组向,要继续往上找*/
    public TreeNode LCA2(TreeNode root ,TreeNode n1,TreeNode n2){
        if (root == null || root == n1 || root == n2){
            return root;
        }
        TreeNode left=LCA2(root.left,n1,n2);
        TreeNode right=LCA2(root.right,n1,n2);
        if (left != null && right != null){
            //这个说明head是最初的汇聚点
            return root;
        }
        /*左右俩个树,谁不为空返回谁*/
        return left!=null?left:right;
    }

    /*找这棵树的后继节点---默认这棵树是有父亲节点的*/
    /*public TreeNode getSuccessTreeNode(TreeNode node){
        if (node == null)return node;
        *//*第一种情况*//*
        if (node.right != null){
            while (node.left !=null){
                node=node.left;
            }
            return node;
        }else {
            *//*第二种情况: 无右子树*//*
            TreeNode parent=node.parent;
            *//*parent != null这个条件就是判断node是最右节点的情况*//*
            while (parent != null && parent.left != node){
                node=parent;
                parent=node.parent;
            }
            return parent;
        }


    }*/
    /*按照先序序列序列化*/
    public String serialByPre(TreeNode root){
        if (root == null)return "#_";
        String res=root.val+"_";
        res+=serialByPre(root.left);
        res+=serialByPre(root.right);
        return res;
    }
    public TreeNode reconByPreString(String preStr){
        String[] values = preStr.split("_");
        Queue<String> queue=new LinkedList<>();
        for (int i = 0; i != values.length ; i++) {
            queue.add(values[i]);
        }
        return reconPreOrder(queue);
    }
    public TreeNode reconPreOrder(Queue<String> queue){
        String value= queue.poll();
        if (value.equals("#")){
            return null;
        }
        TreeNode node=new TreeNode(Integer.valueOf(value));
        node.left=reconPreOrder(queue);
        node.right=reconPreOrder(queue);
        return node;
    }
    /*折纸问题*/
    public void printALLFolds(int N){
        printProcess(1,N,true);
    }
    /*递归的过程来到某一个节点
    * i是节点的层数,N是一共的层数,flg==true表示是凹  flg==false表示是凸*/
    private void printProcess(int i,int N,boolean flg){
        if (i > N)return;
        printProcess(i+1,N,true);
        System.out.println(flg?"凹":"凸");
        printProcess(i+1,N,false);
    }
    public static class Info3{
        public TreeNode start;
        public TreeNode end;
        public Info3(TreeNode start , TreeNode end){
            this.start =start;
            this.end = end;
        }
    }
    public static Info3 process(TreeNode x){
        if (x == null){
            return new Info3(null,null);
        }
        Info3 leftHead =process(x.left);
        Info3 rightHead = process(x.right);
        if (leftHead.end != null)leftHead.end.right =x;
        x.left =leftHead.end;
        x.right =rightHead.start;
        if (rightHead.start != null)rightHead.start.left =x;
        return new Info3(leftHead.start!=null ?leftHead.start:x,
                rightHead.end!=null?rightHead.end:x);


    }
    public static class Info4{
        public TreeNode maxBSTHead;
        public boolean isBST;
        public int min;
        public int max;
        public int maxBSTSize;

        public Info4(TreeNode maxBSTHead, boolean isBST, int min, int max, int maxBSTSize) {
            this.maxBSTHead = maxBSTHead;
            this.isBST = isBST;
            this.min = min;
            this.max = max;
            this.maxBSTSize = maxBSTSize;
        }
    }
    public static Info4 precess4(TreeNode x){
        if (x == null)return new Info4(null,true,Integer.MIN_VALUE,Integer.MAX_VALUE,0);
        Info4 left = precess4(x.left);
        Info4 right = precess4(x.right);

        int min =x.val;
        int max =x.val;
        int maxBSTsize =0;

        TreeNode maxBSTHead =null;
        if (left != null){
            min=Math.min(left.min,left.min);
            max =Math.max(left.max,left.max);
            maxBSTHead =left.maxBSTHead;
            maxBSTsize = left.maxBSTSize;
        }
        if (right != null){
            min=Math.min(left.min,right.min);
            max =Math.max(left.max,right.max);
        }

        if (right!=null && right.maxBSTSize >maxBSTsize){
            maxBSTHead =right.maxBSTHead;
            maxBSTsize = right.maxBSTSize;
        }
        boolean isBST =false;

        if (
                ((left == null) || left.isBST) && ( (right == null)|| right.isBST)
        ){
            if (   ((left==null)||(left.max<x.val))  && ( (right == null)||(right.min>x.val)) ){
                isBST =true;
                maxBSTHead= x;
                int leftsize = left==null?0: left.maxBSTSize;
                int rightsize = right ==null?0: right.maxBSTSize;
                maxBSTsize =leftsize+rightsize+1;
            }
        }
        return new Info4(maxBSTHead,isBST,min,max,maxBSTsize);



    }
    //输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表
    TreeNode pre, head;
    public TreeNode treeToDoublyList(TreeNode root) {
        if(root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(TreeNode cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(pre != null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
    // 判断B树是不是A树的子树
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null || A == null)return false;
       if (isSameTree(A,B))return true;
       boolean leftF = isSubStructure(A.left,B);
       if (leftF)return true;
       boolean rightF = isSubStructure(A.right,B);
       if (rightF)return true;
       else return false;

    }
    // 判断是不是相同的树
    public boolean isSameTree(TreeNode p,TreeNode q){
        //判断一个节点为空和一个节点不为空的情况
        if (p == null && q!= null || p!=null && q== null)return false;
       /* 子结构的写法,因为B树可能是A树的一部分
       if (p == null && q!= null )return false;
        if(p!=null && q==null)return true;*/
        //判断都是空的情况
        if (p== null && q==null)return true;
        if (p.val != q.val)return false;
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }



    // 根据先序 和中序构建二叉树

//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//
//    }









}
